1

The Othello game on an n × n board is PSPACE-complete

Year:
1994
Language:
english
File:
PDF, 647 KB
english, 1994
2

An hierarchy between context-free and context-sensitive languages

Year:
1970
Language:
english
File:
PDF, 718 KB
english, 1970
10

Some combinatorial game problems require Ω(nk) time

Year:
1984
Language:
english
File:
PDF, 753 KB
english, 1984
11

Left-right trees, a new tree structure for machine translation

Year:
1998
Language:
english
File:
PDF, 214 KB
english, 1998
13

Probabilistic automata push-down

Year:
1989
Language:
english
File:
PDF, 700 KB
english, 1989
14

Gradually intractable problems and nondeterministic log-space lower bounds

Year:
1985
Language:
english
File:
PDF, 1.03 MB
english, 1985
15

The emptiness problem for indexed language is exponential-time complete

Year:
1986
Language:
english
File:
PDF, 650 KB
english, 1986
25

Space complexity in on-line computation

Year:
1982
Language:
english
File:
PDF, 554 KB
english, 1982
31

A characterization of time complexity by simple loop programs

Year:
1980
Language:
english
File:
PDF, 772 KB
english, 1980
39

A polynomial time algorithm to infer sequential machines

Year:
2003
Language:
english
File:
PDF, 999 KB
english, 2003
41

Classes of Pebble Games and Complete Problems

Year:
1979
Language:
english
File:
PDF, 1.29 MB
english, 1979
44

Simultaneous (poly-time, log-space) lower bounds

Year:
1987
Language:
english
File:
PDF, 557 KB
english, 1987
48

Translatability of flowcharts into while programs

Year:
1974
Language:
english
File:
PDF, 733 KB
english, 1974